#include <bits/stdc++.h>

using namespace std;

// 最大平均通过率
// 一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试
// 给你一个二维数组classes，其中classes[i]=[passi, totali]
// 表示你提前知道了第i个班级总共有totali个学生
// 其中只有 passi 个学生可以通过考试
// 给你一个整数extraStudents，表示额外有extraStudents个聪明的学生，一定能通过期末考
// 你需要给这extraStudents个学生每人都安排一个班级，使得所有班级的平均通过率最大
// 一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数
// 平均通过率 是所有班级的通过率之和除以班级数目
// 请你返回在安排这extraStudents个学生去对应班级后的最大平均通过率
// 测试链接 : https://leetcode.cn/problems/maximum-average-pass-ratio/

class Solution 
{
public:
    struct Class
    {
        double pass, total, ratio;
        // 大根堆用小于号进行比较
        bool operator<(const Class& other) const
        {
            return ratio < other.ratio;
        }
    };

    double maxAverageRatio(vector<vector<int>>& classes, int m) 
    {
		int n = classes.size();
		// Class c1 : {pass, total, ratio}
		// pass : c1班级有多少人通过
		// total : c1班级总人数
		// ratio : 如果再来一人，c1班级通过率提升多少，(pass+1)/(total+1) - pass/total
		// 通过率提升的大根堆
        priority_queue<Class> heap;
        for(auto& c : classes)
        {
            double pass = c[0], total = c[1];
            heap.push(pass, total, (pass + 1) / (total + 1) - pass / total);
        }
		// 天才一个一个分配，看将这些天才分配到哪里去通过率更高
		// m * logn
        while(m--)
        {
            Class cur = heap.top();
            heap.pop();
            double pass = cur.pass + 1;
            double total = cur.total + 1;
            heap.push(pass, total, (pass + 1) / (total + 1) - pass / total);
        }
        // 计算通过率累加和
        double ans = 0;
        while(!heap.empty())
        {
            Class cur = heap.top();
            heap.pop();
            ans += cur.pass / cur.total;
        }
        // 返回最大平均通过率
        return ans / n;
    }
};